package leetcode.N1001_N1100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/14 2:04 下午
 */
public class N1002 {

    public List<String> commonChars(String[] A) {
        int length = A.length;
        if (length == 0) {
            return new ArrayList<>();
        }
        // 当前结果集
        char[] currentList = A[0].toCharArray();
        Arrays.sort(currentList);
        for (int i = 1; i < length; i++) {
            currentList = mergeSame(currentList, A[i]);
            if (currentList.length == 0) {
                return new ArrayList<>();
            }
        }
        List<String> result = new ArrayList<>(currentList.length);
        for (char c : currentList) {
            result.add(String.valueOf(c));
        }
        return result;
    }

    private char[] mergeSame(char[] left, String s) {
        StringBuffer sb = new StringBuffer();
        char[] right = s.toCharArray();
        Arrays.sort(right);
        int leftLength = left.length;
        int rightLength = right.length;
        int leftIndex = 0;
        int rightIndex = 0;
        while (leftIndex < leftLength && rightIndex < rightLength) {
            char leftVal = left[leftIndex];
            char rightVal = right[rightIndex];

            if (leftVal == rightVal) {
                sb.append(leftVal);
                leftIndex++;
                rightIndex++;
            } else if (leftVal > rightVal) {
                rightIndex++;
            } else {
                leftIndex++;
            }
        }
        return sb.toString().toCharArray();
    }
}
